// https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/description/

// 算法思路总结：
// 1. 动态规划处理最多k次交易的股票问题
// 2. f[i][j]表示第i天完成j次交易且持有股票的最大利润
// 3. g[i][j]表示第i天完成j次交易且不持有股票的最大利润
// 4. 时间复杂度：O(nk)，空间复杂度：O(nk)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <climits>

class Solution 
{
public:
    const int INF = 0x3f3f3f3f;
    int maxProfit(int k, vector<int>& prices) 
    {
        int m = prices.size();
        if (m == 0) return 0;
        if (m == 1) return 0;
        k = min(k, m / 2);

        vector<vector<int>> f(m, vector<int>(k + 1, -INF));
        vector<vector<int>> g(m, vector<int>(k + 1, -INF));

        f[0][0] = -prices[0], g[0][0] = 0;
        for (int i = 1 ; i < m ; i++)
        {
            for (int j = 0 ; j < k + 1; j++)
            {
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if (j - 1 >= 0) 
                    g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
            }
        }

        int maxVal = INT_MIN;
        for (int i = 0 ; i < k + 1 ; i ++)
            maxVal = max(maxVal, g[m - 1][i]);

        return maxVal;
    }
};

int main()
{
    int k1 = 2, k2 = 2;
    vector<int> v1 = {2,4,1}, v2 = {3,2,6,5,0,3};
    Solution sol;

    cout << sol.maxProfit(k1, v1) << endl;
    cout << sol.maxProfit(k2, v2) << endl;

    return 0;
}